package recursionToDP;

import org.junit.Test;

import java.util.*;

/*
 * 熟悉  课堂上 所有出现过的  递归 明白  清楚 每一步 
 * 不会 递归 不 可能  搞懂  动态规划
 * 一个递归函数  可以 通过增加 参数的 过程  就可以 增加 更多的可能性  进而 增加 更多的 功能
 *1.打印 一个字符串的 全部子序列  
 *2. 打印 一个字符串 不重复的 全部子序列
 *3.打印一个字符串 的全排列 
 *4. 不重复的 全排列
 *上面 这 几个题 直接 回溯 法 解决  没必要 按照 他这种方法   按照 卡尔 的方法 (如果 剪枝操作的 化 必须 要 排序了)
 *5. 给你一个 栈 用递归 给它 逆序 
 *
 * 
 */
public class Brecursion {
	static int a;
	public static void main(String []args) {
		//Stack<Integer> s=new Stack<>();
		//hanio1(3);
		System.out.println();
		//hanio2(3,"left","right","mid");
		String str = "abc";
//		printSubString(str);
//		LinkedList<Character> path;
//		path.remove();
//		System.out.println();
//		printSubStringUnrepeat(str);
		System.out.println(a);
	}

	// 要 或 者 不要 的  的选择 性问题 （二叉树的 递归版本）
	public void backTracingBianry(int index,String str, StringBuilder sb , Deque<String> ans){
			if(index == str.length()){
				ans.addLast(sb.toString());
				return ;
			}
			// choose current element!
			sb.append(str.charAt(index));
			backTracingBianry(index + 1,str,sb,ans);
			sb.deleteCharAt(sb.length() - 1);
			// no choose current element!
			backTracingBianry(index + 1,str,sb,ans);
	}
	@Test
	public void test1(){
		// 注意 还有个  空 字符串序列 （什么 字符 都不选择！）
		String str = "abcb";
		Deque<String> ans = new ArrayDeque<>();
		backTracingBianry(0,str,new StringBuilder(),ans);
		System.out.println(ans);
		//
		mutiplyTree(0,str,new StringBuilder());
		System.out.println("heloo");
		char[] chars = str.toCharArray();
		Arrays.sort(chars);
		mutiplyTreeUnRepeat(0,chars,new StringBuilder());

	}




	/*
	 再补充 一个 多叉树的 版本！
	 注意这种子序列的问题，有点不一样
	 对于多叉树的 版本， 在 节点 处， 就要 收集 结果
	 不同于 二叉树递归版本的  ， 叶子节点 处，才收集 结果
	 一定要区分这点！
	 下面这个代码是正确的！
	 */
	public void mutiplyTree(int index,String str,StringBuilder sb){
		// 在所有的 节点处 ，直接 就 打印结果！
		System.out.print(sb.toString() + " ");
		if(index == str.length()){
			return ;
		}
		for(int i = index;i < str.length();i++){
			sb.append(str.charAt(i));
			mutiplyTree(i + 1,str,sb);
			sb.deleteCharAt(sb.length() - 1);
//			System.out.println(sb.toString());
		}
	}



	// 下面是个去重版本
	/*
	  这个 题 ，有点特殊，
	  子序列 ，是涉及 到 顺序的，那排序 不都乱套了嘛
	  去重 还是交给 set 吧
	  set 的话， 就又 不 能剪枝 了
	  这种序列问题是不能排序的！
	 */
	public void mutiplyTreeUnRepeat(int index,char[] str,StringBuilder sb){
		System.out.print(sb.toString() + " ");
		if(index == str.length){
			return ;
		}
		for(int i = index;i < str.length;i++) {
			if(i > index && str[i] == str[i - 1]){
				continue;
			}
			sb.append(str[i]);
			mutiplyTreeUnRepeat(i + 1, str, sb);
			sb.deleteCharAt(sb.length() - 1);
		}
	}



	//打印一个 字符串的  全部 子序列 ;  递归 就是 回溯  回溯 就是递归  去重的  话 肯定要  排序的 首先
	//  这好像 不太对啊  子序列 并不是 子集  吧   但我这 求的 是  子集啊  
	//  这个 好像 不太 好搞  啊  先把 去重的的  代码 写出来吧     真的 写出来 还真是 不太容易啊 
	public static void printSubStringUnrepeat(String s) {
		//List<Character> path = new LinkedList<>();//  这还玩的是多态 
		LinkedList<Character> path =new LinkedList<>();
		List<List<Character>> ans =new ArrayList<>();//  多态
		char [] str= s.toCharArray();
		Arrays.sort(str);
		backTracingUnreapeat(0,str,path,ans);
		for(List<Character> list :ans) {
			System.out.println(list);
		}
		
	}
	public static void backTracingUnreapeat(int index,char []s,LinkedList<Character> path,List<List<Character>> ans) {
		  //  basecase 
		if(index==s.length) {
			ans.add(new LinkedList<>(path));
			return ;
		}
		//  先在  这个 地方标记一下 
		for(int i = index;i<s.length;i++) {
			// 去重的代码  这里 很吊  这是其中的 一种  方法  还有一种 就是 用 used  数组 来 去重
			if(i > index && s[i]==s[i-1]) {
				continue;
			}
//			backTracingUnreapeat(i+1 , s ,path.add(s[i]), ans);
			//  这个 add 方法 作为 一个 方法  返回得 是 Boolean  值  参数都对应不上啊 
			path.add(s[i]);
			backTracingUnreapeat(i+1 , s ,path, ans);
			path.removeLast();
		}
	}

	/*
	使用多叉树递归 ，来求 子序列 是错误的（是 指 在 叶子 节点， 收集结果是错误的！）
	写法 ，目前来看是的
	 */
	@Test
	public void test2(){
		String str = "abbc";
		printSubStringUnrepeat(str);
	}

	/*
	==
	到达basecase 相当于 走到了 叶子节点
	叶子节点的上面（也就是 刚进入 递归函数的时候，） 是 节点
	所以 要注意最终收集 结果 是在 叶子节点， 还是 节点处
	---
	  全排列问题 ： 结果肯定是在 叶子节点进行收集的！
	  这里 全排列的 去重还是 很关键的！
	  =======
	  这里去重 并没有使用 set
	  直接 在 递归的时候， 去重（顺便 还起到了 剪枝的作用！）
	 */
	public void allShow(String str,StringBuilder sb,boolean [] used){
		if(sb.length() == str.length()){
			System.out.print(sb.toString() + " ");
			return ;
		}
		/*
		  注意 一下 这个 set 数组的作用
		  ASCII 码的 值 是 0 ~ 255
		  在当前 层 来说！
		  如果当前的 层 的某个 字符  x 用过了，那直接 跳过 就行了！
		  避免重复， 这里 去重手段 ，是很秒的
		  这个数组的改变 是 不用 回溯的
		  因为 set 数组 只存活于 当前层的 递归！

		  used : 来控制 同一 枝干上 不能重复用（之前使用过的）
		  set： 来控制 同一树层 上， 不能使用之前出现过的字符
		  这样理解就很简单了！
		  这里的 set数组  相当于 一个 map 的作用
		  个人 感觉这里使用map 会更加合适！
		 */
		boolean[] set = new boolean[256];
		for(int i = 0;i < str.length();i++){
			if(!used[i] && !set[str.charAt(i)]){
				sb.append(str.charAt(i));
				used[i] = true;
				set[str.charAt(i)] = true;
				allShow(str,sb,used);
				sb.deleteCharAt(sb.length() - 1);
				used[i] = false;
			}
		}
	}
	// 也可以是 这种写法！， 多 整个 index 参数！
	// 这个 index， 没有什么 其他的作用 ，只有一个 计数 的作用
	public void allShow1(int index ,String str,StringBuilder sb,boolean [] used){
		if(index == str.length()){
			System.out.print(sb.toString() + " ");
			return ;
		}
		for(int i = 0;i < str.length();i++){
			if(!used[i]){
				sb.append(str.charAt(i));
				used[i] = true;
				allShow1(index + 1,str,sb,used);
				sb.deleteCharAt(sb.length() - 1);
				used[i] = false;
			}
		}
	}
	@Test
	public void test3(){
		String str = "acc";
		boolean [] used = new boolean[str.length()];
		allShow(str,new StringBuilder(),used);
		System.out.println();
		allShow1(0,str,new StringBuilder(),used);
	}


	
	
	//hanio  版本二 直接 一个递归 函数 解决
	//  通过 增加 递归的  参数直接 把 抽象的六个函数 直 接归一  增加参数 增加 递归函数的功能
	public static void hanio2(int n,String from,String to,String other) {
		if(n==1) {
			System.out.println("1 from "+from+ "to "+to);
			return ;
		}
		hanio2(n-1,from,other,to);
		System.out.println(n+" from "+from+ "to "+to);
		hanio2(n-1,other,to,from);
	}
	
	//1. hanio 汉诺塔 问题    汉诺塔  这真的 就是 为递归 而设计的  一个东西  这种解法 是 直接 把 汉诺塔啊问题 拆解成 很多小问题
	// 去解决 
	public static void hanio1(int n) {
		leftToRight(n);
	}
	public static void leftToRight(int n) {
		if(n==1) {
			System.out.println("1 from left to right ");
			return ;
		}
		leftToMid(n-1);
		System.out.println(n+" from left to right ");
		midToRight(n-1);
	}
	public static void midToRight(int n) {
		if(n==1) {
			System.out.println("1 from mid to right ");
			return ;
		}
		midToLeft(n-1);
		System.out.println(n+" from mid to right ");
		leftToRight(n-1);
	}
	public static void midToLeft(int n) {
		if(n==1) {
			System.out.println("1 from mid to left ");
			return ;
		}
		midToRight(n-1);
		System.out.println(n+" from mid to left ");
		rightToLeft(n-1);
	}
	public static void rightToLeft(int n) {
		if(n==1) {
			System.out.println("1 from right to left ");
		    return ;
		}
		rightToMid(n-1);
		System.out.println(n+" from right to left ");
		midToLeft(n-1);
	}
	public static void rightToMid(int n) {
		if(n==1) {
			System.out.println("1 from right to mid ");
			return ;
		}
		rightToLeft(n-1);
		System.out.println(n+" from right to mid ");
		leftToMid(n-1);
	}
	public static void leftToMid(int n) {
		if(n==1) {
			System.out.println("1 from left to mid ");
			return ;
		}
		leftToRight(n-1);
		System.out.println(n+" from left to  mid");
		rightToMid(n-1);
	}

	//5. 逆序一个栈   果然 一个 递归是解决不掉的
	/*
	这个题 很考验 递归函数 的设计
	首先 要明确 一点， 一个 递归函数 肯定是做不到的
	，因为递归 函数的 过程 和  栈 的 过程是一样的！
	所以 整两个递归函数
	f ---> 主 递归函数，负责 逆序，需要： 在 第一层递归的时候 获得栈底的元素， 以此类推
	g ---> 返回 栈 底的元素(只返回 栈底的元素)
	综合 一下，发现 就可以实现了
	 */
	public int g(Stack<Integer> stack){
		if(stack.size() == 1){
			return stack.pop();
		}
		int temp = stack.pop();
		int last = g(stack);
		stack.push(temp);
		return last;
	}
	// f  说实话， 主要是 上面 这个 g 函数 很抽象！
	public void f(Stack<Integer> stack){
		if(stack.isEmpty()){
			return ;
		}
		int reverse = g(stack);
		f(stack);
		stack.push(reverse);
	}

	// test
	@Test
	public void test4(){
		Stack<Integer> stack = new Stack<>();
		for(int i = 1;i <= 5;i++){
			stack.push(i);
		}
		f(stack);
		System.out.println(stack);
	}
}
